Primal-dual interior point approach for computingl 1-solutions andl ∞-solutions of overdetermined linear systems

This paper concerns solving an overdetermined linear systemA ^T x=b in the leastl ₁-norm orl -norm sense, whereA ^m×n ,m<n. We show that the primal-dual interior point approach for linear programming can be applied, in an effective manner, to linear programming versions of thel ₁ andl -problems. The resulting algorithms are simple to implement and can attain quadratic or superlinear convergence rate. At each iteration, the algorithms must solve a linear system with anm×m positive-definite coefficient matrix of the formADA ^T , whereD is a positive diagonal matrix. The preliminary numerical results indicate that the proposed algorithms offer considerable promise.This research was supported in part by Grants NSF DMS-91-02761 and DOE DE-FG05-91-ER25100.     

Interior-point algorithm for quadratically constrained entropy minimization problems

In this paper, we develop an interior point algorithm for quadratically constrained entropy problems. The algorithm uses a variation of Newton's method to follow a central path trajectory in the interior of the feasible set. The primal-dual gap is made less than a given in at most steps, wheren is the dimension of the problem andm is the number of quadratic inequality constraints.     

A quadratically convergent O(\sqrt n L)-iteration algorithm for linear programming

Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.Supported in part by NSF Grant DDM-8922636 and NSF Coop. Agr. No. CCR-8809615, the Iowa Business School Summer Grant, and the Interdisciplinary Research Grant of the University of Iowa Center for Advanced Studies.Supported in part by NSF Coop. Agr. No. CCR-8809615, AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Supported in part by NSF Grant DMS-9102761 and DOE Grant DE-FG05-91ER25100.     

Ketu and the second invariant of a quadratic space

Using the Chern classes defined by Grothendieck, we map aK-theoretic invariant of invertible symmetric matrices defined by Giffen to the Clifford invariant.According to Herrmann Graßman'sWörterbuch zum Rig-veda, Ketu may not be connected with K₂ but es bezeichnet das, was sich sichtbar oder kenntlich macht ...     

C 1 surface interpolation with constraints

Givenn pairwise distinct and arbitrarily spaced pointsP _i in a domainD of thex–y plane andn real numbersf _i, consider the problem of computing a bivariate functionf(x, y) of classC ¹ inD whose values inP _i are exactlyf _i,i=1,,n, and whose first or second order partial derivatives satisfy appropriate equality and inequality constraints on a given set ofp pointsQ _l inD.In this paper we present a method for solving the above problem, which is designed for extremely large data sets. A step of this method requires the solution of a large scale quadratic programming (QP) problem.The main purpose of this work is to analyse an iterative method for determining the solution of this QP problem: such a method is very efficient and well suited for parallel implementation on a multiprocessor system.Work supported by MURST Project of Computational Mathematics, Italy.     

Strategies for measurements of pseudocontact shifts in protein NMR spectroscopy.

Paramagnetic metal ions bound to proteins generate a dipolar field that can be accurately probed by pseudocontact shifts (PCS) displayed by the protein's nuclear spins. PCS are highly useful for determining the coordinates of individual spins in the molecule and for rapid structure determinations of entire protein-protein and protein-ligand complexes. However, PCS measurements require reliable resonance assignments for the molecule in its paramagnetic state and in a diamagnetic reference state. This article discusses different approaches for pairwise resonance assignments, with emphasis on a strategy which exploits chemical exchange between the two states.     

Mixed strategy solutions forN-person quadratic games

Mixed strategy -equilibrium points are given forN-person games with cost functions consisting of quadratic, bilinear, and linear terms and strategy spaces consisting of closed balls in Hilbert spaces. The results are applied to linear-quadratic differential games with no information and quadratic integral constraints on the control functions.This work was supported by a Commonwealth of Australia, Postgraduate Research Award.     

The alternating basis algorithm for assignment problems

The purpose of this paper is to present a new primal extreme point algorithm for solving assignment problems which both circumvents and exploits degeneracy. The algorithm is based on the observation that the degeneracy difficulties of the simplex method result from the unnecessary inspection of alternative basis representations of the extreme points. This paper characterizes a subsetQ of all bases that are capable of leading to an optimal solution to the problem if one exists. Using this characterization, an extreme point algorithm is developed which considers only those bases inQ. Computational results disclose that the new algorithm is substantially more efficient than previously developed primal and primal-dual extreme point (simplex) methods for assignment problems.     

Infrared intensities of liquids XXV: Dielectric constants, molar polarizabilities and integrated intensities of liquid toluene at 25 °C between 4800 and 400 cm

The main purpose of this paper is to present accurate infrared integrated intensities of liquid toluene, C₆H₅CH₃, at 25 °C. Also presented are the decadic molar absorption coefficients, E_m, the real and imaginary dielectric constants, ε′ and ε″, and the real and imaginary molar polarizabilities, ^′_m and ^″_m. Integrated intensities were determined as C_j, the area under bands in the spectrum, for all bands between 4800 and 440 cm⁻¹. The contributions from the different bands were separated by fitting the spectrum with classical damped harmonic oscillator bands. The uncertainties in the integrated intensities of most bands are estimated to be 5–10%, with the uncertainties in very weak bands and in shoulders possibly up to 100%. The intensity that should be assigned to the fundamentals is more difficult to estimate due to Fermi resonance with overtone and combination bands, and a best estimate is given. The integrated intensities of the fundamental vibrations and the corresponding transition dipole moments are summarized and are compared with literature values for the gas.     

Efficient algorithms for solving rank two and rank three bilinear programming problems

Finitely convergent algorithms for solving rank two and three bilinear programming problems are proposed. A rank k bilinear programming problem is a nonconvex quadratic programming problem with the following structure: % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4baFfea0dXde9vqpa0lb9% cq0dXdb9IqFHe9FjuP0-iq0dXdbba9pe0lb9hs0dXda91qaq-xfr-x% fj-hmeGabaqaciGacaGaaeqabaWaaeaaeaaakeaaieaacaWFTbGaa8% xAaiaa-5gacaWFPbGaa8xBaiaa-LgacaWF6bGaa8xzaiaa-bcacaWF% 7bacbiGaa43yamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+Hhaca% GFRaGaa4hzamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+LhacaGF% RaWaaabuaeaacaGFJbWaa0baaSqaaiaa+PgaaeaacaGF0baaaOGaam% iEaiabl+y6NjaadsgadaqhaaWcbaGaamOAaaqaaiaadshaaaGccaWG% 5bGaaiiFaaWcbaGaa8NAaiaa-1dacaWFXaaabeqdcqGHris5aOGaa4% hEaiabgIGiolaa+HfacaGFSaGaa4xEaiabgIGiolaa+LfacaWF9bGa% a8hlaaaa!5D2E!\[minimize \{ c_0^t x + d_0^t y + \sum\limits_{j = 1} {c_j^t xd_j^t y|} x \in X,y \in Y\} ,\]where X Rⁿ¹ and Y R ⁿ² are non-empty and bounded polytopes. We show that a variant of parametric simplex algorithm can solve large scale rank two bilinear programming problems efficiently. Also, we show that a cutting-cake algorithm, a more elaborate variant of parametric simplex algorithm can solve medium scale rank three problems.This research was supported in part by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. 63490010.